package game;

import java.util.Arrays;

/**
 * 完美洗牌问题
 * 给定一个长度为偶数的数组arr，长度记为2*州N。前N个为左部分，后N个为右部分。arr就可以表示为{L1,L2,. . , Ln,R1,R2,. . , Rn},
 * 请将数组调整成{R1,L1,R2,L2,. . , Rn,Ln}的样子。
 *
 * @author Liaorun
 */
@SuppressWarnings("AlibabaUndefineMagicConstant")
public class ShuffleProblem {

    public static void main(String[] args) {

        // 3,1,4,2
        int[] ints = {1, 2, 3, 4};
        shuffle(ints);
        System.out.println(Arrays.toString(ints));

        // 4,1,5,2,6,3
        int[] ints1 = {1, 2, 3, 4, 5, 6};
        shuffle(ints1);
        System.out.println(Arrays.toString(ints1));

    }

    /**
     * 获取数组中的数，在完美洗牌后的位置
     *
     * @param i   原来的位置
     * @param len 数组的长度
     * @return 洗牌后的位置
     */
    public static int modifyIndex1(int i, int len) {
        if (i <= len / 2) {
            return 2 * i;
        } else {
            return 2 * (i - (len / 2)) - 1;
        }
    }

    /**
     * 获取数组中的数，在完美洗牌后的位置
     *
     * @param i   原来的位置
     * @param len 数组的长度
     * @return 洗牌后的位置
     */
    public static int modifyIndex2(int i, int len) {
        return (2 * i) % (len + 1);
    }


    public static void shuffle(int[] arr) {
        // 完美洗牌问题，数组长度必须偶数
        if (arr != null && arr.length != 0 && (arr.length & 1) == 0) {
            shuffle(arr, 0, arr.length - 1);
        }
    }

    /**
     * 在arr[l..r]上做完美洗牌的调整
     *
     * @param arr
     * @param l
     * @param r
     */
    private static void shuffle(int[] arr, int l, int r) {
        // 切成一块块的解决，没一块的长度满足（3^k) - 1
        while (r - l + 1 > 0) {
            int len = r - l + 1;
            int base = 3;
            int k = 1;

            // 找到当前可以切的最大块
            while (base <= (len + 1) / 3) {
                base *= 3;
                k++;
            }
            // 当前要解决长度为base - 1的块，一半就是在除2
            int half = (base - 1) / 2;
            // [l..r]的中点位置
            int mid = (l + r) / 2;

            // 要旋转的左边部分为[l+half...mid],右边部分为arr[mid + 1..mid+half]
            // 注意在这里，arr下标是从0开始的
            rotate(arr, l + half, mid, mid + half);
            // 旋转完成后，从L开始算，长度为base - 1的部分进行下标连续推
            cycles(arr, l, base - 1, k);

            // 解决了前base - 1的部分，剩下部分继续处理
            l = l + base - 1;
        }
    }

    /**
     * 从start位置开始，往右len的长度这一段，做下标连续推
     * 出发位置 依此为 1，3，9.。。（3^n)
     *
     * @param arr   数组
     * @param start 操作数组开始位置
     * @param len   操作数组长度
     * @param k     开始位置的个数
     */
    private static void cycles(int[] arr, int start, int len, int k) {
        // 找到每一个出发位置trigger,一共k个
        // 每一个trigger都进行下标连续推
        // 出发位置是从1开始算的，而数组下标是从0开始算的
        for (int i = 0, trigger = 1; i < k; i++, trigger *= 3) {
            int preValue = arr[trigger + start - 1];
            int cur = modifyIndex1(trigger, len);

            // 跳出条件，再次回到起始位置
            while (cur != trigger) {
                int temp = arr[cur + start - 1];
                arr[cur + start - 1] = preValue;
                preValue = temp;
                cur = modifyIndex1(cur, len);
            }
            arr[cur + start - 1] = preValue;
        }
    }

    /**
     * 交换数组中两段连续位置的顺序
     * <p>
     * step1：数组一使用双指针逆序
     * step2: 数组二使用双指针逆序
     * step3: 整段数组使用双指针逆序
     *
     * @param arr   数组
     * @param start 第一段开始的位置
     * @param mid   第一段结束的位置
     * @param end   第二段结束的位置
     */
    private static void rotate(int[] arr, int start, int mid, int end) {

        reverse(arr, start, mid);
        reverse(arr, mid + 1, end);
        reverse(arr, start, end);
    }


    public static void reverse(int[] arr, int start, int end) {

        // 跳出条件：两个指针没有相遇就交换，
        // 原来自己写的是开始指针到中点就跳出，代码复杂，中点还没找对
        while (start < end) {
            int temp = arr[start];
            arr[start++] = arr[end];
            arr[end--] = temp;
        }
    }

}
